Detecting changes to memory is useful in many areas. One example is in virtualized computer systems, and a more specific example, occurs in an area involving Universal Serial Bus (USB) devices.
Most operating systems include a Universal Serial Bus (USB) controller which facilitates bidirectional communication between a USB client driver and a connected USB device. Because the USB is a widespread standard, in virtualized computer systems, most guest operating systems include a guest USB controller driver designed to function with most, if not all, compliant USB controllers and a virtual USB controller (the virtual USB controller can implement the functionality of a physical USB controller such as facilitating bidirectional communication between a USB client driver and a connected USB device). In appropriate designs, the virtual USB controller will appear to the guest USB controller driver as if it were a physical USB controller, and the fact that the controller is virtualized will be transparent to the guest USB controller driver.
In the USB standard, a USB controller driver communicates with a USB controller through a frame list topology stored in various shared memory locations. Depending on the type of USB controller, the frame list topology can include data structures such as a frame list, a Transfer Descriptor (TD), and/or Queue Headers (QH). Thus, in a virtualized computer system, the guest USB controller driver and the virtual USB controller can communicate by manipulating the data structures of the frame list topology.
To provide functionality normally provided by a physical USB controller, the virtual USB controller should recognize changes to the frame list topology. One method for detecting changes to the frame list topology is to traverse the frame list topology, and compare it to frame list topologies traversed previously. However, frequently traversing the frame list topology consumes time and resources. Furthermore, in many cases the frame list topology will not have changed at all since the last traversal, making frequent traversals inefficient.